package sort;

import java.util.List;

/*
* 148. 排序链表
*       给链表排序使用归并排序: 自顶向下的归并排序空间复杂度O(N),自底向上复杂度O(1)
*
* */
class ListNode{
    int val;
    ListNode next;
    public ListNode(){}
    public ListNode(int val){
        this.val=val;
    }
    public ListNode(int val,ListNode next){
        this.val=val;
        this.next=next;
    }

}
public class SortList148 {
//    // 自顶向下的归并排序
//    public ListNode sortList(ListNode head) {
//        return sortList(head,null);
//    }
//
//    private ListNode sortList(ListNode head, ListNode tail) {
//        if(head==null){
//            return head;
//        }
//        if(head.next==tail){
//            head.next=null;
//            return head;
//        }
//        ListNode fast=head,slow=head;
//        while(fast!=tail){
//            slow=slow.next;
//            fast=fast.next;
//            if(fast!=tail){
//                fast=fast.next;
//            }
//        }
//        ListNode mid=slow;
//        ListNode listNode1 = sortList(head, mid);
//        ListNode listNode2 = sortList(mid, tail);
//        return merge(listNode1,listNode2);
//    }
//
//    private ListNode merge(ListNode list1, ListNode list2) {
//        ListNode dummyHead=new ListNode(0);
//        ListNode tmp=dummyHead,tmp1=list1,tmp2=list2;
//        while(tmp1!=null && tmp2!=null){
//            if(tmp1.val<=tmp2.val){
//                tmp.next=tmp1;
//                tmp1=tmp1.next;
//            }else {
//                tmp.next=tmp2;
//                tmp2=tmp2.next;
//            }
//           tmp=tmp.next;
//        }
//        if(tmp1==null){
//            tmp.next=tmp2;
//        }
//        if(tmp2==null){
//            tmp.next=tmp1;
//        }
//        return dummyHead.next;
//    }
    //自底向上的归并排序
//    public ListNode sortList(ListNode head) {
//
//    }
}
